A conventional instruction cache or data cache includes a tag array to store information identifying the cache lines that are stored in the cache and a data array to store the data for the cache line. When the cache receives a request to read a memory location, the cache uses the memory address to look up the cache line in the tag array. A data lookup can also be used to read the data stored in the cache line out of the data array. The tag array lookup and the data array lookup can be performed sequentially. For example, the tag array lookup may be performed and, if the request hits in the tag array, the data array lookup may subsequently be performed. The tag array lookup is typically performed in a multi-stage pipeline and so the cache will not know whether the tag array lookup hit or missed in the tag array until several cycles after the tag array pipeline has begun executing the tag array lookup. The data array lookup is therefore delayed by several cycles when it is performed sequentially with the tag array lookup. For example, a data array lookup request may be delayed by 10 cycles for a 1 MB cache and 12 cycles for a 2 MB cache when they are performed sequentially with the tag array lookup request.
The tag array lookup and the data array lookup can also be performed in parallel. For example, the tag array lookup may be picked for execution in the tag array pipeline in the same cycle (or with a fixed one cycle delay) in which the data array lookup is picked for execution in the data array pipeline. However, the data array lookup cannot be picked for execution unless the data array pipeline has resources available to process the data array lookup. If the data array pipeline resources are not available at the time the tag array lookup is picked for execution, the data array lookup request is not performed in parallel with the tag array lookup and instead must be performed sequentially with the tag array lookup request. Consequently, many data array lookup requests are delayed by several cycles when the data array pipeline resources are not available.
While the disclosed subject matter may be modified and may take alternative forms, specific embodiments thereof have been shown by way of example in the drawings and are herein described in detail. It should be understood, however, that the description herein of specific embodiments is not intended to limit the disclosed subject matter to the particular forms disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the scope of the appended claims.